package com.xz.sort.cmp;

import com.xz.sort.Sort;

/**
 * @author XZ
 * @create 2021-12-10 15:10
 */
public class ASelfQuickSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        sort(0,array.length);
    }

    /**
     *
     * @param begin 开始位置
     * @param end 结束位置+1
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;
        int mid = pivotIndex(begin, end);
        sort(begin, mid);
        sort(mid + 1, end);
    }

    /**
     *
     * @param begin
     * @param end
     * @return
     */
    private int pivotIndex(int begin, int end) {
        T savedValue = array[begin];
        boolean flag = true;
        end--;
        while (end > begin) {//排序
            if (flag) {//flag = true;从右往左搜索
                if (cmp(savedValue, array[end]) >= 0) {//savedValue>array[end]
                    array[begin] = array[end];
                    begin++;
                    flag = false;
                } else {
                    end--;
                }
            } else {//flag = false;从右往左搜索
                if (cmp(savedValue, array[begin]) > 0) {//savedValue>array[begin]
                    begin++;
                } else {
                    array[end] = array[begin];
                    end--;
                    flag = true;
                }
            }
        }
        //begin=end
        array[begin] = savedValue;
        return end;
    }
}